package interview.linked;

/**
 * 环长
 */
public class CycleLength {
    /**
     * 链表有环 求环长
     * @param node 传入开始节点
     * @return 返回环长
     */
    public static int cycleLength(Node node){
        int length = 0;
        Node p1 = node;
        Node p2 = node;
        //为了找到第一次相遇的位置
        while(p1 != null && p1.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) break;
        }
        //从第一次相遇位置继续走 因为p2两倍的速度与p1所以在此相遇之后 p2比p1多走一圈 也就是环的长度
        while(true){
            length ++;
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) break;
        }
        return length;
    }
}
